import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 207. Course Schedule 课程表
 * https://leetcode.com/problems/course-schedule/
 */
class CourseSchedule {
    /**
     * 方法：使用深度优先搜索（DFS）检测图中是否有环来判断课程是否能够完成
     * 
     * Args:
     *   numCourses: int - 课程总数
     *   prerequisites: int[][] - 课程依赖关系数组，每个元素[a,b]表示要完成a需要先完成b
     * 
     * Returns:
     *   boolean - 如果所有课程都能完成返回true，否则返回false
     * 
     * Time: O(V+E) - V是课程数量，E是依赖关系数量
     * Space: O(V+E) - 需要存储邻接表和颜色数组
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //构建领接表
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        //计算入度
        int[] inDegree = new int[numCourses];
        for(int[] pair : prerequisites){
            int a = pair[0], b = pair[1];
            adj.get(b).add(a);
            inDegree[a]++;
        }
        // 初始化队列
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i< numCourses; i++){
            if(inDegree[i] == 0){
                queue.offer(i);
            }
        }
        // 拓扑排序
        int count = 0;
        while(!queue.isEmpty()){
            int node = queue.poll();
            count++;
            for(int neighbor : adj.get(node)){
                inDegree[neighbor]--;
                if(inDegree[neighbor] == 0){
                    queue.offer(neighbor);
                }
            }
        }
        return count == numCourses;
    }

    /**
     * 方法：使用拓扑排序检测图中是否有环来判断课程是否能够完成
     * 
     * Args:
     *   numCourses: int - 课程总数
     *   prerequisites: int[][] - 课程依赖关系数组，每个元素[a,b]表示要完成a需要先完成b
     * 
     * Returns:
     *   boolean - 如果所有课程都能完成返回true，否则返回false
     * 
     * Time: O(V+E) - V是课程数量，E是依赖关系数量
     * Space: O(V+E) - 需要存储邻接表和入度数组
     */
    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        List<Integer>[] g = new ArrayList[numCourses];
        Arrays.setAll(g, i -> new ArrayList<>());
        for(int[] p: prerequisites){
            g[p[1]].add(p[0]);
        } 
        int[] colors = new int[numCourses];
        for(int i = 0; i < numCourses; i++){
            if(colors[i] == 0 && dfs(i, g, colors)){
                return false; // 有环
            }
        }
        return true; // 没有环
    }

    private boolean dfs(int x, List<Integer>[] g, int[] colors){
        colors[x] = 1;// x 正在访问中
        for(int y : g[x]){
            if(colors[y] == 1 || colors[y] == 0 && dfs(y, g, colors)){
                return true; // 找到了环
            }
        }
        colors[x] = 2; // x 完全访问完毕
        return false; // 没有找到环
    }
    
}